package com.practice.niuke.new_direct_practice.class11;

import java.util.Arrays;
import java.util.HashSet;

/**
 * 先给出可整合数组的定义:如果一个数组在排序之后，每相邻两个数差的绝对值
 * 都为 1， 则该数组为可整合数组。例如，[5,3,4,6,2]排序之后为[2,3,4,5,6]，
 * 符合每相邻两个数差的绝对值 都为 1，所以这个数组为可整合数组。 给定一个
 * 整型数组 arr，请返回其中最大可整合子数组的长度。例如， [5,5,3,2,6,4,3]
 * 的最大 可整合子数组为[5,3,2,6,4]，所以返回 5。
 */
public class Code05_LongestIntegratedLength {

    /**
     * 方法一：暴力解法（TODO：视频中讲的第一种方法, 时间复杂度O(N^3)）
     * 求最长可整合子数组的长度的暴力解法
     *
     * @param arr arr
     * @return int
     */
    public static int getLIL1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int len = 0;
        for (int start = 0; start < arr.length; start++) {// 子数组所有可能的开头
            for (int end = start; end < arr.length; end++) {// 开头为start的情况下，所有可能的结尾
                if (isIntegrated(arr, start, end)) {// 判断arr[start...end]是不是可整合的
                    len = Math.max(len, end - start + 1);
                }
            }
        }
        return len;
    }

    /**
     * 判断一个数组中的一个子数组是不是可整合数组，时间复杂度O(N)
     *
     * @param arr   源数组
     * @param left  子数组的开始位置
     * @param right 子数组的结束位置
     * @return boolean
     */
    public static boolean isIntegrated(int[] arr, int left, int right) {
        int[] newArr = Arrays.copyOfRange(arr, left, right + 1); // O(N)
        Arrays.sort(newArr); // O(N*logN)
        for (int i = 1; i < newArr.length; i++) {
            if (newArr[i - 1] != newArr[i] - 1) {
                return false;
            }
        }
        return true;
    }

    /**
     * 方法一：求最长可整合子数组的长度的优化解法（TODO：视频中讲的第二种方法, 时间复杂度O(N^2)）
     * 优化判断一段数组（子数组）是否为可整合的方法：
     * 子数组为childen[]，
     * （1）如果Childen中有重复值，Childen一定是不可整合的
     * （2）当Childen中没有重复值时，
     *    如果Childen中的最大值为ChildenMax,Childen中的最小值为ChildenMin，
     *    ChildenMax-ChildenMin==Childen.length-1，则Childen一定是可整合的
     *
     * @param arr arr
     * @return int
     */
    public static int getLIL2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int len = 0;
        int max = 0;
        int min = 0;
        // 该set用于判断有没有重复值
        HashSet<Integer> set = new HashSet<Integer>();
        for (int L = 0; L < arr.length; L++) { // L 左边界，开始位置start
            set.clear();
            max = Integer.MIN_VALUE;
            min = Integer.MAX_VALUE;
            for (int R = L; R < arr.length; R++) { //  R 右边界，结束位置end
                //  arr[L..R]这个子数组在验证

                if (set.contains(arr[R])) {
                    // arr[L..R]上开始 出现重复值了，arr[L..R往后]不需要验证了，
                    // 一定不是可整合的
                    break;
                }
                // arr[L..R]上无重复值
                set.add(arr[R]);
                max = Math.max(max, arr[R]);
                min = Math.min(min, arr[R]);
                if (max - min == R - L) { // L..R 是可整合的
                    len = Math.max(len, R - L + 1);
                }
            }
        }
        return len;
    }

    public static void main(String[] args) {
        int[] arr = {5, 5, 3, 2, 6, 4, 3};
        System.out.println(getLIL1(arr));
        System.out.println(getLIL2(arr));

    }

}
